'''
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
解题思路： 后续遍历最后一个元素即为根节点
          所以从头开始遍历查找大于根节点的元素，根据二叉搜索书的特点，左子树 小于根节点 根节点小于右子树。所以从不满足条件处
          分段进行递归验证
'''


class Solution:
    def verifySquenceofBST(self, sequence):
        if sequence is None or len(sequence) == 0:
            return False
        length = len(sequence)
        root = sequence[-1]

        for i in range(length):
            if sequence[i] > root:
                break

        for j in range(i, length):
            if sequence[j] < root:
                return False

        left, right = True, True
        if 0 < i < (length - 1):
            left = self.verifySquenceofBST(sequence[:i])
            right = self.verifySquenceofBST(sequence[i:-1])
        return right and left


s = Solution()
print(s.verifySquenceofBST([4,8,6,12,16,14,10]))